package com.gwcloud.leetcode.tags.dp;

/** 
* @ClassName   : Leetcode0198 
* @author      : ganwei 
* @date        : 2020年5月18日 
* @Description : TODO 
*/
public class Leetcode0198 {
	/**
	 * -解题思路，动态规划思路，有点暴力的
	 */
	public int rob(int[] nums) {
		int n = nums.length;
		int[][] dp = new int[n+1][2];
		for(int i = 1; i <= n; i++) {
			dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
			dp[i][1] = dp[i-1][0] + nums[i-1];
		}
		
		return Math.max(dp[n][0], dp[n][1]);
	}
	/**
	 * -解题思路，优化版动态规划
	 */
	public int rob_1(int[] nums) {
		int n = nums.length;
		int[] dp = new int[n+2];
		for(int i = n-1; i >= 0; i--) {
			dp[i] = Math.max(dp[i+1], nums[i] + dp[i+2]);
		}
		return dp[0];
	}
	
	public static void main(String[] args) {
		Leetcode0198 l0198 = new Leetcode0198();
		int[] nums = {1,2,3,1};
		System.out.println(l0198.rob_1(nums));
	}
}
